#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//----------------------- 顺序表进行初始化、查找、插入和删除等基本操作-------------------
#define SEQ_SIZE 10
typedef int DataType;

typedef struct seqnode
{
    DataType data[SEQ_SIZE];
    int length;
} SeqNode, *SeqList;

SeqList createSeqList(int len)
{
    SeqList L = (SeqList)malloc(sizeof(SeqNode));
    L->length = len;
    for (int i = 0; i < SEQ_SIZE; i++)
    {
        L->data[i] = 0;
    }
    return L;
}

void insertSeqList(SeqList L, int position, DataType value)
{
    if (L == NULL)
    {
        printf("list not be allow null\n");
        return;
    }
    // printf("range%d=, =%d=\n", position, L->length);
    if (position < 1 || position > L->length - 1)
    {
        printf("position error! out of range\n");
        return;
    }

    if (L->length >= SEQ_SIZE)
    {
        printf("list length out of maxsize\n");
        return;
    }

    // 从最后开始移动
    for (int i = L->length - 1; i >= position - 1; i--)
    {
        // 将前一位移动到后一位
        L->data[i + 1] = L->data[i];
    }

    L->data[position - 1] = value;
    L->length++;
}

DataType findValueByLoca(SeqList L, int position)
{
    for (int i = 0; i < L->length; i++)
    {
        if (i == (position - 1))
        {
            return L->data[i];
        }
    }
    return -1;
}

DataType deletSeqList(SeqList L, int position)
{
    if (L == NULL)
    {
        printf("list not be allow null\n");
        exit(0);
    }
    if (position < 1 || position > L->length)
    {
        printf("position error! out of range\n");
        exit(0);
    }

    DataType value = L->data[position - 1];
    for (int i = position - 1; i < L->length - 1; i++)
    {
        L->data[i] = L->data[i + 1];
    }
    L->length--;
    return value;
}

void printArray(SeqList L)
{
    printf("\nSeqList=[ ");
    for (int i = 0; i < L->length; i++)
    {
        printf("%d ", L->data[i]);
    }
    printf("]\n");
}

//-----------------------单链表进行初始化、查找、插入和删除等基本操作-------------------
typedef struct slinknode
{
    char data;
    struct slinknode *next;
} SLinkNode, *SLinkList;

void printSLinkListBase(SLinkList *SL)
{
    printf("---------------SLinkList=[ ");
    SLinkList temp = (*SL);
    while (temp != NULL)
    {
        printf("%c", temp->data);
        temp = temp->next;
        if (temp != NULL)
        {
            printf("->");
        }
    }
    printf(" ]\n");
}

void printSLinkList(SLinkList SL)
{
    printSLinkListBase(&SL);
}

// 不带头结点. 头插法
SLinkList createSLinkList()
{
    SLinkList head = NULL;
    SLinkNode *temp;

    printf("===>input element for create link list: ");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        temp = (SLinkList)malloc(sizeof(SLinkNode));
        temp->data = ch;
        temp->next = head;
        // 新结点永远在前面
        head = temp;
    }
    return head;
}

// 不带头结点. 尾插法
SLinkList createSeqLinkList()
{
    SLinkList head = NULL;

    SLinkNode *tail;
    SLinkNode *temp;
    printf("===>input element for create link list: ");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        temp = (SLinkList)malloc(sizeof(SLinkNode));
        temp->data = ch;
        if (head == NULL)
        {
            head = temp;
        }
        else
        {
            tail->next = temp;
        }
        tail = temp;
    }

    if (tail != NULL)
    {
        tail->next = NULL;
    }
    return head;
}

// 带头结点. 尾插法
SLinkList createSLinkListHasHead()
{
    SLinkList head = (SLinkList)malloc(sizeof(SLinkNode));
    head->data = 'H';

    SLinkNode *tail = head;
    SLinkNode *temp;

    printf("===>input element for create link list: ");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        temp = (SLinkList)malloc(sizeof(SLinkNode));
        temp->data = ch;
        tail->next = temp;
        tail = temp;
    }

    tail->next = NULL;
    return head;
}

void insertHasHeadLinkList(SLinkList SL, int position, char value)
{
    SLinkNode *temp = SL;

    // 将指针移动到插入的位置
    int counter = 0;
    while (temp != NULL && position - 1 > counter)
    {
        temp = temp->next;
        counter++;
    }
    // 若移动到链尾则说明超出插入范围
    if (temp == NULL)
    {
        printf("out of range!\n");
        exit(0);
    }

    SLinkNode *node = (SLinkNode *)malloc(sizeof(SLinkNode));
    node->data = value;
    // 新结点的下一个结点指针原结点的下一个结点
    node->next = temp->next;
    temp->next = node;
}

void insertLinkList(SLinkList *SL, int position, char value)
{
    SLinkNode *temp = (*SL);
    if (temp == NULL)
    {
        printf("it's empty linklist!\n");
        exit(0);
    }

    int counter = 1;
    SLinkNode *node = (SLinkNode *)malloc(sizeof(SLinkNode));
    node->data = value;
    if (position == counter)
    {
        node->next = temp;
        (*SL) = node;
        // printSLinkListBase(SL);
        return;
    }

    while (temp != NULL && position - 1 > counter)
    {
        temp = temp->next;
        counter++;
    }

    if (temp == NULL)
    {
        printf("out of range!\n");
        exit(0);
    }

    node->next = temp->next;
    temp->next = node;
}

char deleteHasHeadLinkList(SLinkList SL, int position)
{
    SLinkNode *temp = SL;

    int counter = 1;
    while (temp != NULL && position - 1 > counter)
    {
        temp = temp->next;
        counter++;
    }

    if (temp == NULL)
    {
        printf("error! unable to delete \n");
        exit(0);
    }

    SLinkNode *node = temp->next;
    temp->next = node->next;
    char value = node->data;
    free(node);
    return value;
}

char findHasHeadLinkList(SLinkList SL, int position)
{
    SLinkNode *temp = SL->next;
    int index = 1;
    while (temp != NULL && temp->next != NULL && index < position)
    {
        temp = temp->next;
        index++;
    }

    if (index == position)
    {
        return temp->data;
    }

    if (temp == NULL || temp->next == NULL)
    {
        printf("not found element!\n");
    }
    return '\0';
}

//-----------------------一些简单应用问题，如进制转换、字符串输入等，利用栈或队列来实现-------------------
typedef struct stack
{
    char *array;
    int top;
    unsigned int capacity;
} Stack, *SeqStack;

SeqStack createSeqStack(unsigned int size)
{
    SeqStack S = (SeqStack)malloc(sizeof(Stack));
    S->capacity = size;
    S->top = -1;
    S->array = (char *)malloc(S->capacity * sizeof(char));
    return S;
}

int fullSeqStack(SeqStack S)
{
    return S->top == S->capacity - 1;
}

int emptySeqStack(SeqStack S)
{
    return S->top == -1;
}

void push(SeqStack S, char value)
{
    if (fullSeqStack(S))
    {
        printf("stack is full!\n");
        return;
    }
    // S->top = S->top + 1;
    S->array[++S->top] = value;
}

char pop(SeqStack S)
{
    if (emptySeqStack(S))
    {
        printf("stack is empty!\n");
        exit(0);
    }

    char value = S->array[S->top];
    S->top--;
    return value;
}

char getStackFirst(SeqStack S)
{
    if (emptySeqStack(S))
    {
        printf("stack is empty!\n");
        exit(0);
    }

    return S->array[S->top];
}

typedef struct queue
{
    char *array;
    int front; // 队头
    int rear;  // 队尾
    unsigned int capacity;
} Queue, *SeqQueue;

SeqQueue createSeqQueue(unsigned size)
{
    SeqQueue Q = (SeqQueue)malloc(sizeof(Queue));
    Q->capacity = size;
    Q->front = Q->rear = 0;
    Q->array = (char *)malloc(Q->capacity * sizeof(char));
    return Q;
}

int fullSeqQueue(SeqQueue Q)
{
    return Q->front == (Q->rear + 1) % Q->capacity;
}

int emptySeqQueue(SeqQueue Q)
{
    return Q->front == Q->rear;
}

void enQueue(SeqQueue Q, char value)
{
    // 进队列, 从队尾进。仅与队尾相关
    if (fullSeqQueue(Q))
    {
        printf("queue is full\n");
        exit(0);
    }

    Q->array[Q->rear] = value;
    Q->rear = (Q->rear + 1) % Q->capacity;
}

char deQueue(SeqQueue Q)
{
    if (emptySeqQueue(Q))
    {
        printf("queue is empty!\n");
        exit(0);
    }
    char value = Q->array[Q->front];
    Q->front = (Q->front + 1) % Q->capacity;
    return value;
}

char getQueueFirst(SeqQueue Q)
{
    if (emptySeqQueue(Q))
    {
        printf("queue is empty!\n");
        exit(0);
    }
    return Q->array[Q->front];
}

// ------ 二叉链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历及求所有叶子和结点个数的操作等------
typedef struct blnode
{
    char data;
    struct blnode *lchild;
    struct blnode *rchild;
} BLNode, *BinLinkTree;

BinLinkTree createByComplete()
{
    BLNode *Q[100];

    BLNode *cur;
    BinLinkTree BLT = NULL;

    int front = 1, rear = 0;

    printf(">>input char element: ");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        cur = NULL;
        if (ch != '@')
        {
            cur = (BinLinkTree)malloc(sizeof(BLNode));
            cur->data = ch;
            cur->lchild = cur->rchild = NULL;
        }

        rear++;
        Q[rear] = cur;
        if (rear == 1)
            BLT = cur;
        else
        {
            // 当前结点不为null且出队列不为null
            if (cur != NULL && Q[front] != NULL)
            {
                if (rear % 2 == 0)
                    Q[front]->lchild = cur;
                else
                    Q[front]->rchild = cur;
            }

            if (rear % 2 != 0)
                front++;
        }
    }

    return BLT;
}

void preOrder(BinLinkTree BLT)
{
    if (BLT == NULL)
    {
        return;
    }

    printf("%c ", BLT->data);
    preOrder(BLT->lchild);
    preOrder(BLT->rchild);
}

void inOrder(BinLinkTree BLT)
{
    if (BLT == NULL)
    {
        return;
    }

    inOrder(BLT->lchild);
    printf("%c ", BLT->data);
    inOrder(BLT->rchild);
}

void postOrder(BinLinkTree BLT)
{
    if (BLT == NULL)
    {
        return;
    }

    postOrder(BLT->lchild);
    postOrder(BLT->rchild);
    printf("%c ", BLT->data);
}

void levelTraversal(BinLinkTree BLT)
{
    if (BLT == NULL)
    {
        return;
    }
    BinLinkTree temp = BLT;
    // 模拟队列
    BLNode *Q[100];

    int front = 0, rear = 0;

    printf("%c", temp->data);
    Q[rear] = temp;
    rear++;

    while (front != rear)
    {
        temp = Q[front];
        front++;
        if (temp->lchild != NULL)
        {
            printf("%c", temp->lchild->data);
            Q[rear] = temp->lchild;
            rear++;
        }

        if (temp->rchild != NULL)
        {
            printf("%c", temp->rchild->data);
            Q[rear] = temp->rchild;
            rear++;
        }
    }
}

int treeMaxDepth(BinLinkTree BLT)
{
    if (BLT == NULL)
        return 0;

    int leftDepth = treeMaxDepth(BLT->lchild);
    int rightDepth = treeMaxDepth(BLT->rchild);

    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

int findElement(BinLinkTree BLT, char value)
{
    if (BLT == NULL)
        return 0;

    if (BLT->data == value)
        return 1;

    int founded = findElement(BLT->lchild, value);
    if (founded)
        return 1;

    return findElement(BLT->rchild, value);
}

int countLeafNodes(BinLinkTree BLT)
{
    if (BLT == NULL)
    {
        return 0;
    }

    if (BLT->lchild == NULL && BLT->rchild == NULL)
    {
        return 1;
    }

    return countLeafNodes(BLT->lchild) + countLeafNodes(BLT->rchild);
}

int countAllNodes(BinLinkTree BLT)
{
    if (BLT == NULL)
    {
        return 0;
    }

    return 1 + countAllNodes(BLT->lchild) + countAllNodes(BLT->rchild);
}

//-------------------------采用邻接矩阵或邻接表作为存储结构，完成有向图和无向图的DFS和BFS操作------------------

//--------------------------实现顺序查找、折半查找及二叉排序查找算法，比较他们的查找速度。------------------

typedef struct bstnode
{
    int key;                // 关键字
    struct bstnode *lchild; // 左子树指针
    struct bstnode *rchild; // 右子树指针
} BSTNode, *BSTree;

// 二叉排序树插入元素
BSTree insertBST(BSTree BST, int key)
{
    // 二叉排序树为空，则新插入结点则作为根结点。否则必为叶子结点
    if (BST == NULL)
    {
        BSTNode *newNode = (BSTree)malloc(sizeof(BSTNode));
        newNode->key = key;
        newNode->lchild = newNode->rchild = NULL;
        return newNode;
    }

    // 若插入元素小于 当前结点元素，则插入左子结点
    if (key < BST->key)
        BST->lchild = insertBST(BST->lchild, key);
    else if (key > BST->key)
        BST->rchild = insertBST(BST->rchild, key);

    return BST;
}

BSTree buildBSTree(int array[], int len)
{
    BSTree root = insertBST(root, array[0]);
    for (int i = 1; i < len; i++)
        insertBST(root, array[i]);
    return root;
}

BSTNode *searchBSTNode(BSTree BST, int key)
{
    if (BST == NULL)
        return NULL;

    if (key == BST->key)
        return BST;

    if (key < BST->key)
        return searchBSTNode(BST->lchild, key);

    return searchBSTNode(BST->rchild, key);
}

//-------------------------实现直接插入、冒泡、直接选择、快速、堆、归并排序。比较各种排序算法的运行速度------------------
